import java.util.Arrays;
import java.util.Scanner;
public class Main {
    // 定义一个常量，表示无限大，表示初始状态下两个点之间没有路径
    static final int N = Integer.MAX_VALUE;

    // Dijkstra 算法的实现
    public static void dijkstra(int[] dis, int n, boolean[] str, int[][] g) {
        // 初始化所有点的距离为无限大，表示不可达
        Arrays.fill(dis, N);
        // 起点到自己的距离是 0
        dis[1] = 0;

        // 循环 n 次，保证每个点都被处理一次
        for (int i = 0; i <= n; i++) {
            int t = -1;
            // 找出距离起点最近且尚未被处理的点
            for (int j = 1; j <= n; j++) {
                // 如果该点未被处理且距离更短，选择该点
                if (!str[j] && (t == -1 || dis[j] < dis[t])) {
                    t = j;
                }
            }

            // 如果没有找到符合条件的点，结束算法
            if (t == -1) break;

            // 更新与 t 相邻的点的最短路径
            for (int j = 1; j <= n; j++) {
                if (g[t][j] != N) { // 只有在存在路径的情况下更新
                    dis[j] = Math.min(dis[j], dis[t] + g[t][j]);
                }
            }
            // 标记 t 为已处理
            str[t] = true;
        }

        // 输出结果
        System.out.println("点1到其他点的最短路径：");
        for (int i = 1; i <= n; i++) {
            // 如果某个点的距离依然是初始值，说明该点不可达
            if (dis[i] == N) {
                System.out.println("点1 -> 点" + i + ": 不可达");
            } else {
                // 否则输出最短路径的距离
                System.out.println("点1 -> 点" + i + ": " + dis[i]);
            }
        }
    }

    // 主函数
    public static void main(String[] args) {
        // 定义数组，保存是否已经处理过的点
        boolean[] str = new boolean[1005];
        // 定义数组，保存从起点到每个点的最短路径
        int[] dis = new int[1005];
        // 邻接矩阵，保存每对点之间的边的权值
        int[][] g = new int[1005][1005];

        // 初始化邻接矩阵，所有点之间的距离初始化为无限大
        for (int i = 0; i < 1005; i++) {
            Arrays.fill(g[i], N);
        }

        // 创建扫描器用于输入
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入点的个数：");
        int n = sc.nextInt();  // 输入点的数量
        System.out.println("请输入边的个数：");
        int m = sc.nextInt();  // 输入边的数量

        // 读取每一条边的信息并更新邻接矩阵
        while (m > 0) {
            System.out.println("请输入起始点");
            int x = sc.nextInt();  // 起点
            System.out.println("请输入终点");
            int y = sc.nextInt();  // 终点
            System.out.println("请输入它们之间的距离");
            int z = sc.nextInt();  // 边的权值
            // 更新起点到终点的距离（如果有多条边取最小的距离）
            g[x][y] = Math.min(g[x][y], z);
            m--;
        }

        // 调用 Dijkstra 算法计算最短路径
        dijkstra(dis, n, str, g);
    }
}
